#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int val = 0, ListNode *nt = NULL): val(val), next(nt) {}
};

class palindrome {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;

        while (left < right) {
            if (s[left] != s[right])
                return false;
            left++;
            right--;
        }
        return true;
    }

    string getPalindrome(string s, int l, int r) {
        while (l >= 0 && r < s.size() && s[l] == s[r]) {
            l--;
            r++;
        }
        return s.substr(l + 1, r - l - 1);
    }

    bool isPalindromeList(ListNode *head) {
        // 将链表反转存入新链表，然后比较
        ListNode *headForCompare = NULL, *cur = head;
        while (cur != NULL) {
            ListNode *temp = new ListNode(cur->val, headForCompare);
            headForCompare = temp;
            cur = cur->next;
        }
        cur = head;
        ListNode *cur2 = headForCompare;
        while (head != NULL) {
            if (cur->val != cur2->val)
                return false;
            cur = cur->next;
            cur2 = cur2->next;
        }
        return true;
    }

    bool isPalindromeTree(ListNode *head) {
        // 利用二叉树后序遍历比较
        left = head;
        return traverse(head);
    }

    bool traverse(ListNode *right) {
        if (right == NULL) return true;
        // 递归过程实现栈，利用栈进行比较
        bool res = traverse(right->next);
        res = res && (left->val == right->val);
        left = left->next;
        return res;
    }

    bool isPalindromeO1(ListNode *head) {
        if (head == nullptr) 
            return true;
        
        ListNode *slow, *fast;
        ListNode *p, *q;
        slow = fast = head;
        // 找到链表中点
        while (fast != nullptr && fast->next != nullptr) {
            if (fast->next->next == nullptr)
                p = slow;
                // 记录下链表反转回来的位置
            fast = fast->next->next;
            slow = slow->next;
        }
        if (fast != nullptr)
            slow = slow->next;
        
        // 反转链表，然后比较元素
        ListNode *left = head;
        ListNode *right = reverse(slow);
        q = right;
        while (right != nullptr) {
            if (left->val != right->val)
                return false;
            left = left->next;
            right = right->next;
        }
        // 将链表反转回来
        p->next = reverse(q);
        return true;
    }

    ListNode *reverse(ListNode *head) {
        ListNode *pre = NULL;
        ListNode *cur, *next;
        cur = next = head;
        
        while (cur != NULL) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

private:
    ListNode *left;
};